Multidimensional Array
Recently, I came upon a need for a multidimensional array. I immediately turned to Google to see if I could locate something already designed, coded, and tested. To my dismay, I found only a smattering of hints, discussions, and some skeletal code (e.g. www.computer-programming-forum.com/21-eiffel and then look for multidimensional array and a submitter named "ralmi").
The need in the use case before me did not magically "go away", so I needed to code something. Using an "array-of-array's" was not kosher because the ARRAY and ARRAYED_LIST classes et al did not provide me with a clean and simple API. Using the skeletal code found on the computer programming forum, I decided to see if I could make a well crafted class with a simple API. Below is what I came up with.
On quick self-review, I can see that there is a potential bug if the boundaries of any dimension of the array are <= 0. I am not managing these ranges properly. The assumption is that all array boundaries are > 1.
Calling the API is pretty simple:
test_arrayn
-- New test routine
local
l_array_n: ARRAYN [INTEGER]
do
create l_array_n.make_n_based (<<[1,2], [1,2], [1,2]>>)
create l_array_n.make_one_based (<<2, 2, 2>>)
end
Once the ARRAYN is created (e.g. l_array_n), then it is open for access:
local
l_item: MY_ITEM
l_array_n: ARRAYN [MY_ITEM]
do
create l_array_n.make_one_based (<<3,3,3>>)
l_array_n.put (create {MY_ITEM}, <<1,2,3>>)
l_item := l_array_n.item (<<1,2,3>>)
end
note
description: "[
Representation of a Multi-dimensional Array.
]"
date: "$Date: $"
revision: "$Revision: $"
class
ARRAYN [G -> ANY]
create
make_n_based,
make_n_based_filled,
make_one_based,
make_one_based_filled
feature {NONE} -- Initialization
make_one_based_filled (a_nb: ARRAY [INTEGER]; v: G)
-- Initialize Current as a one-based lower bound on all dimensional vectors
-- and then filled with `v'.
do
make_one_based (a_nb)
across 1 |..| internal_items.count as ic_index loop
internal_items.put (v, ic_index.item)
end
end
make_one_based (a_nb: ARRAY [INTEGER])
-- Initialize Current as a one-based lower bound on all dimensional vectors.
local
l_bounds: like bounds
i: INTEGER
do
create l_bounds.make_filled ([0, 0], 1, a_nb.count)
from i := 1
until i > a_nb.count
loop
l_bounds.put ([1, a_nb [i]], i)
i := i + 1
end
make_n_based (l_bounds)
end
make_n_based_filled (a_nb: like bounds; v: G)
-- Initialize Current filled with `v' items and with `a_nb' like `bounds'
do
make_n_based (a_nb)
across 1 |..| internal_items.count as ic_index loop
internal_items.put (v, ic_index.item)
end
end
make_n_based (a_nb: like bounds)
-- Initialize Current with `a_nb' like `bounds'.
local
l_element_count, l_plane_count, i: INTEGER
do
from
bounds := a_nb
i := 1
l_element_count := 1
until
i > a_nb.count
loop
l_plane_count := ((a_nb [i].upper_nb - a_nb [i].lower_nb) + 1)
l_element_count := l_element_count * l_plane_count
i := i + 1
end
create internal_items.make_filled (create {ANY}, 1, l_element_count)
end
feature -- Access
bounds: ARRAY [TUPLE [lower_nb, upper_nb: INTEGER]]
-- Lower and Upper bounds of Current.
dimensions: INTEGER
-- Number of dimensions in Current `bounds'
do
Result := bounds.count
end
max_size: INTEGER
-- Maximum linear size of `internal_items'.
--| Contract support for revealing maximum linear size for Clients of Current.
local
i: INTEGER
once
from
i := 1
Result := 1
until
i > dimensions
loop
Result := Result * bounds [i].upper_nb
i := i + 1
end
end
item (a_vector: ARRAY [INTEGER]): G
-- Item @ `a_vector'.
require
is_valid_vector: is_valid_vector (a_vector)
do
check attached_as_g: attached {G} internal_items [location (a_vector)] as al_item then
Result := al_item
end
end
is_valid_vector (a_vector: ARRAY [INTEGER]): BOOLEAN
-- Is `a_vector' valid, based on `bounds'?
do
Result := a_vector.count <= dimensions
Result := Result and across a_vector as ic_vector
all
ic_vector.item >= bounds [ic_vector.cursor_index].lower_nb and
ic_vector.item <= bounds [ic_vector.cursor_index].upper_nb
end
Result := Result and location (a_vector) <= max_size
end
put (a_object: G; a_vector: ARRAY [INTEGER])
-- Put `object' at `index'
require
is_valid_vector: is_valid_vector (a_vector)
do
internal_items.put (a_object, location (a_vector))
end
location (a_vector: ARRAY [INTEGER]): INTEGER
-- The linear location of element in `internal_items' at `a_vector'.
require
is_valid_vector: is_valid_vector (a_vector)
local
i: INTEGER
do
from
i := 1
Result := 1
until
i > dimensions
loop
Result := Result * a_vector [i]
i := i + 1
end
end
feature {NONE} -- Implementation
internal_items: ARRAY [ANY]
-- Internal storage of items for Current.
;end
A Deeper Flaw than I Thought
Turns out that there is a deeper flaw than I originally thought with the code above. I am working on a correction now and will hopefully have it coded up soon.
The problem is with the calculation of `location': Vector <<1, 2, 1>> is the same location Result as <<2, 1, 1>> -- that is -- 1 x 2 x 1 = 2 and 2 x 1 x 1 = 2. In a 3-dimensional array, this will cause and error, which is precisely what happened when I finally added a precondition to inspect the target location element in the internal_items array to ensure it was empty (e.g. not attached {G} item (a_vector)).
So, what I have to do now is develop and internal structure that is more careful about where it places the items in the internal_items array. I am told that the C compiler does this with the code it generates. I will need to explore and perhaps exploit this algorithm.
The actual solution ...
place (a_object: G; a_vector: ARRAY [INTEGER]) -- Place `a_object' at an empty `a_vector' location. require empty_location: not attached {G} item (a_vector) do put (a_object, a_vector) ensure placed: attached {G} item (a_vector) as al_item and then al_item ~ a_object end replace (a_object: G; a_vector: ARRAY [INTEGER]) -- Place or replace `a_object' at `a_vector' location. do put (a_object, a_vector) end put (a_object: G; a_vector: ARRAY [INTEGER]) -- Put `a_object' at `a_vector' require is_valid_vector: is_valid_vector (a_vector) do internal_items.put (a_object, location (a_vector)) ensure item_at_location: internal_items [location (a_vector)] ~ a_object end location (a_vector: ARRAY [INTEGER]): INTEGER -- The linear location of element in `internal_items' at `a_vector'. require two_or_more: dimensions > 1 is_valid_vector: is_valid_vector (a_vector) local i, l_segment_size: INTEGER do from i := 1 l_segment_size := max_size until i = dimensions loop l_segment_size := (l_segment_size / (bounds [i].upper_nb - bounds [i].lower_nb + 1)).truncated_to_integer Result := Result + l_segment_size * (a_vector [i] - bounds [i].lower_nb) i := i + 1 end Result := Result + a_vector [i] end